1. Field of the Invention
The present invention relates to route searching methods an apparatus, and more particularly to a method and an apparatus for searching for the most suitable route between two arbitrarily specified points on certain road network data.
2. Description of the Background Art
In recent years, with the development of electronics, the navigation apparatus for guiding vehicles have spread rapidly. Some conventional navigation apparatus are equipped with a route searching apparatus for automatically searching for the most suitable route from a starting point to a destination (the shortest distance route or the minimum time route).
In the conventional route searching apparatus, known methods for obtaining the most suitable route for guiding vehicles include the automatic vehicle guiding method disclosed in Japanese Patent Laid-Open No.59-105113, for example. This method obtains the most suitable route between a starting point and a destination from road network data representing a network of roads by using the Dijkstra method, one of the optimum route determining methods. The theory of the Dijkstra method is described in "Data Structures and Algorithms" written by A. V. Aho et al. and translated by Yoshio Ono, Kabushiki Kaisha Baihu-kan, 1990, pp.179-183, for example.
When searching for the most suitable route between two arbitrary points on a network of roads according to the above-mentioned method, the time for obtaining the route increases as the numbers of intersections and roads included in the road network increase. As a result, the user must wait for a longer time (e.g., about two or three minutes), which leads to inconvenience.
Hence, like the route searching methods disclosed in Japanese Patent Laid-Open No.2-56591 and Japanese Patent Laid-Open No.3-54590, for example, there is a method which searches for the most suitable route by using map data having a hierarchical structure to reduce the calculating time. However, even when this method is used, there are limitations in the reduction of the time for searching the road network (about 30-60 seconds), and therefore further reduction of the searching time is demanded.
Accordingly, for the aim of reducing the searching operation, Japanese Patent Laid-Open No.4-204482 presents a method in which routes between individual intersections on a map are previously obtained and recorded. In this method, when a starting point and a destination are inputted, intersections near the points are searched for and the route between the searched intersections is retrieved and displayed. This method can show the route to a user by taking time only to retrieve the route between an intersection closest to the starting point and an intersection closest to the destination from the previously stored route data.
However, since the number of intersections in Japan, even only of those in networks of roads wide enough to allow vehicles to pass each other, i.e., 5.5 m or wider, amounts to about sixty-five thousand, it is absolutely impossible to record routes between all of the intersections. Even if the previously recorded routes are limited to main roads such as prefectural roads and national roads, the number of the intersections amounts to ten thousand or more in the entire country, so it is still difficult to record routes between all points.